package main.java.indi.zyj.c150.window;

import java.util.HashMap;
import java.util.Map;

public class _02_CheckInclusion {
    public boolean checkInclusion(String s1, String s2) {
        int len = s2.length();

        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> needs = new HashMap<>();

        for (char c : s1.toCharArray()){
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, valid = 0;

        while (right < len){

            // 获取进入窗口的元素
            char c = s2.charAt(right);

            // 扩大窗口形成【）的形式，避免边界问题
            right++;

            // 如果是需要的
            if (needs.containsKey(c)){
                // 更新窗口里的needs的值
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果更新的值的个数和needs中c的个数相同，证明窗口里c的个数已经够用，valid++
                if (window.get(c).equals(needs.get(c))){
                    valid++;
                }
            }

            // 如果窗口长度大于s1的长度就要收缩
            if((right - left) >= s1.length()){
                if (valid == needs.size()){
                    return true;
                }
                // 获取窗口左边的数
                char leftChar = s2.charAt(left);
                left++;
                // 判断窗口左边的数是否在needs内
                if (needs.containsKey(leftChar)){
                    // 如果个数相同，valid--，因为needs需要的一个字符不一定只有一个
                    if (window.get(leftChar).equals(needs.get(leftChar))){
                        valid--;
                    }
                    window.put(leftChar, window.get(leftChar) - 1);
                }
            }

        }

        return false;
    }

    public static void main(String[] args) {
    }


}
